package arithmetic;

import utils.PrintUtil;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;

/**
 * Created by AJie on 2019/7/30
 * Function :15. 三数之和
 * 给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。
 * <p>
 * 注意：答案中不可以包含重复的三元组。
 * <p>
 * 例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，
 * <p>
 * 满足要求的三元组集合为：
 * [
 * [-1, 0, 1],
 * [-1, -1, 2]
 * ]
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/3sum
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 */
public class A_08_3Sum {
    public static void main(String[] args) {
        List<List<Integer>> lists = threeSum(new int[]{-1,0,1,2,-1,-4,0,0});
        PrintUtil.print(lists);
    }

    /**
     * 打破了，原有的顺序
     *
     * todo 双指针解法。2遍夹逼中间，已理解2019-10-31 14:53:37
     * 作者：guanpengchn
     * 链接：https://leetcode-cn.com/problems/two-sum/solution/hua-jie-suan-fa-15-san-shu-zhi-he-by-guanpengchn/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     *
     * 标签：数组遍历
     * 首先对数组进行排序，排序后固定一个数nums[i]，
     *
     * 再使用左右指针指向nums[i]后面的两端，
     *
     * 数字分别为nums[L]和nums[R]，
     *
     * 计算三个数的和sumsum判断是否满足为 00，满足则添加进结果集
     *
     * 如果nums[i]大于 0，则三数之和必然无法等于 0，结束循环
     * 如果nums[i] == nums[i-1]，则说明该数字重复，会导致结果重复，所以应该跳过
     * 当sum == 0 时，nums[L] == nums[L+1]则会导致结果重复，应该跳过，L++
     * 当sum == 0 时，nums[R] == nums[R−1]则会导致结果重复，应该跳过，R--
     * 时间复杂度：O(n^2)
     *
     * 空间复杂度：
     * O(logN)。我们忽略存储答案的空间，额外的排序的空间复杂度为O(logN)。
     * 然而我们修改了输入的数组 nums，在实际情况下不一定允许，
     * 因此也可以看成使用了一个额外的数组存储了 nums 的副本并进行排序，
     * 空间复杂度为 O(N)。
     *
     * @param nums
     * @return
     */
    public static List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> ans = new ArrayList();
        int len = nums.length;
        if (len<3){
            return ans;
        }
        Arrays.sort(nums);
        for (int i = 0; i < len; i++) {
           if (nums[i]>0)break;//最小值 > 结果 ,break.
           if (i>0 && nums[i-1]==nums[i])continue;//去重。第一个元素。
           int L = i+1;
           int R = len-1;
           while ( L < R ){
               int res = nums[i] + nums[L] + nums[R];
               if (res ==0) {
                   ans.add(Arrays.asList(nums[i],nums[L],nums[R]));
                   while (L < R && nums[L]==nums[L+1])L++;//去重
                   while (L < R && nums[R]==nums[R-1])R--;//去重
                   L++;
                   R--;
               }else if (res>0){
                    R--;
               }else {
                   L++;
               }
           }
        }
        return ans;
    }

    /**
     * 思路 2次 循环
     * 此题 与 2数之和有一个明显区别，找到所有，而不是一个。
     * 方法1、暴力法 3次循环，去重
     * 方法1、第一次固定第一个数，第二次用2数之和。
     * 暂无 方法2 ^_^
     * 执行用时: 11400 ms, 在3Sum的Java提交中击败了【0.97%】】】 的用户
     *
     * 首先排序然后
     * 加入一个set集合去重，去掉最后去重。
     * 2019-1-19 13:47:48执行用时: 【734 ms】, 在3Sum的Java提交中击败了【4.22%】 的用户
     *
     * @param nums
     * @return
     */
    public static List<List<Integer>> myThreeSum(int[] nums) {
        if (nums == null || nums.length < 3) {
            return new ArrayList<>();
        }

        List<List<Integer>> result = new ArrayList<>();
        HashSet<Integer> firstIsCheckSet = new HashSet<Integer>();//检查第一个数
        /**
         * 加入下面的 sameSecondSet 为了应对以下情况
         * 输入：
         * [0,0,0,0]
         * 输出：
         * [[0,0,0],[0,0,0]]
         * 预期：
         * [[0,0,0]]
         */
        HashSet<Integer> sameSecondSet = new HashSet<Integer>();//检查第二、三个数
        Arrays.sort(nums);
        int target = 0;
        //寻找第一个数
        for (int i = 0; i < nums.length; i++) {
            int firstNum = nums[i];
            if (firstIsCheckSet.contains(firstNum)) {//去除重复的数
                continue;
            }

            int twoNumSum = target - firstNum;
            //【所有】 不重复 2个数的和
            HashSet<Integer> thirdNumSet = new HashSet<Integer>();
//            HashSet<Integer> secondNumIsCheckSet = new HashSet<>();//去重 第二个 数
            for (int j = i + 1; j < nums.length; j++) {
                int secondNum = nums[j];
//                if (secondNumIsCheckSet.contains(secondNum)) {//如果第 1 个数检查过 那么忽略
                int thirdNum = twoNumSum - secondNum;

                if (thirdNumSet.contains(thirdNum)) {//如果存在第三个数
                    /**
                     *   * 输入
                     *      * [0,0,0]
                     *      * 输出
                     *      * []
                     *      * 预期结果
                     *      * [[0,0,0]]
                     *      *
                     *  所以加下面一句     && thirdNum!=secondNum
                     */
                    if ((thirdNumSet.contains(secondNum)&& thirdNum!=secondNum)||(secondNum==thirdNum&&sameSecondSet.contains(secondNum))) {//如果第 1 个数检查过 那么忽略
                        continue;
                    }

                    //第三次去重
                /*  输入      [-1,0,1,2,-1,-4]
                    输出      [[-1,1,0],[-1,-1,2],[0,-1,1]]
                    预期结果  [[-1,-1,2],[-1,0,1]]*/
//                    Integer[] tempResult = {firstNum, secondNum, thirdNum};
//                    boolean isRepeat = false;
//                    Arrays.sort(tempResult);
//                    for (List<Integer> mlist: result) {
//                        Integer[] oneArray = (Integer[]) mlist.toArray(new Integer[mlist.size()]);
//                        Arrays.sort(oneArray);
//                        if (isRepeat = Arrays.equals(tempResult,oneArray)){
//                            break;
//                        }
//                    }
//                    if (!isRepeat){
                    System.out.println("first=="+i+"  second=="+j);
                    ArrayList<Integer> integers = new ArrayList<>();
                    integers.add(firstNum);
                    integers.add(thirdNum);
                    integers.add(secondNum);
                    result.add(integers);
//                    }
                    if (secondNum == thirdNum){
                        sameSecondSet.add(secondNum);
                    }
                }
                thirdNumSet.add(secondNum);
//                secondNumIsCheckSet.add(secondNum);
            }
            firstIsCheckSet.add(firstNum);
        }


        return result;
    }

}
